模拟赛题解/2025.9.27 模拟赛

T1-路径（path）

题面

现有一张 $n$ 个点、$m$ 条边的无向连通图，图中没有重边和自环，点和边都从 $1$ 开始标号。初始时，小 $\text{A}$ 在图中结点 $s$ 的位置上。

小 A 想要在图中游走，但他的行动受到一定的限制。具体而言，我们定义他的“一步”移动过程如下：

• 选择他当前所在点的一条邻边，并移动到该边的另外一个点。
• 他可以选择是否删除他刚才选择的边。如果他选择删除该边，那么他之后无法再次经过这条边；如果他选择保留该边，那么这一步移动对他之后的行动没有影响。

小 $\text{A}$ 希望最后恰好剩下 $n−1$ 条边，并且这些边构成一棵树。但由于小 A 非常懒，因此他又希望他的移动不超过 $k$ 步。

请你为他构造一条满足上述要求的路径。数据保证一定有解。

$2\leq n\leq1000,n-1\leq m\leq\frac {n(n-1)}2,1\leq u<v\leq n$。

题解

首先考虑一条路径的代价：设路径长为 $k$，则代价为 $\sum_{i=1}^{k} a_{v_i}$。注意每个点只会被算一次。

考虑 DP，设 $f_{u,v}$ 表示从 $u$ 到 $v$ 的路径代价的最大值。转移就是 $f_{u,v} = \max\{ f_{u,x} + f_{x,v} - a_x \mid (u,x),(x,v)\ \text{为边} \}$。

由于是树，转移可以做，但复杂度太高。

考虑换根：树形 DP。设 $f_u$ 表示以 $u$ 为根子树中，经过 $u$ 的路径最大值。则 $f_u = \max\bigl( a_u, \max_{(u,v)} (f_v + a_u) \bigr)$。

然后 DFS 两遍即可得到全局最优解。

复杂度 $O(n)$。

T2-命题（proposition）

题面

小 $\text{B}$ 有 $n$ 个命题，这些命题按某种顺序从 $1$ 到 $n$ 标号。第 $i$ 个命题可以用两个参数 $x_i,p_i$ 来描述，其中 $1\leq x_i\leq n$，$p_i\in \{0,1\}$。如果 $p_i=1$，那么该命题就表示第 $i$ 个命题为真；如果 $p_i=0$，那么该命题就表示第 $i$ 个命题为假。

小 $\text{B}$ 发现这 $n$ 个命题有一个神奇的性质，存在一种决定每个命题的真假的方式，使得这些命题在逻辑上自洽。形式化地，存在一个长度为 $n$ 的 $01$ 序列 $q$，使得对于每个 $i\in [1,n]$ 都满足 $q_{x_i}=q_i\oplus 1\oplus p_i$，其中 $\oplus$ 表示异或。

然而有一天，小 B 忘记了每个 $x_i$ 的取值。他想知道每个 $x_i$ 在 $[1,n]$ 中任意取值所得到的 $n^n$ 种方案中，满足上述神奇性质的方案有多少种。

可怜的小 B 并不会这个问题，所以他来求助你。由于答案可能很大，他只需要你告诉他答案对 $998244353$ 取模的结果。

$1\leq n\leq5000$。

题解

考虑一个排列 $p$，其逆序对数为 $\mathrm{inv}(p) = \sum_{1 \leq i < j \leq n} [p_i > p_j]$。

题目要求的其实是统计逆序对数 $\equiv m \pmod{k}$ 的排列个数。

设 $F(n,m)$ 为答案。考虑插入 $n$ 的位置：若放在第 $i$ 个位置，则贡献 $n-i$。因此有转移： $F(n,m) = \sum_{i=1}^n F(n-1,(m-n+i)\bmod k)$。

这就是经典的排列逆序对计数问题的同余版本。

用 DP 或多项式生成函数均可，复杂度 $O(nk)$。

T3-三元组（triple）

题面

给定一个长度为 $n$ 的序列 $a$，元素从 $1$ 开始标号。

定义一个由整数构成的三元组 $(x,y,z)$ 是合法的，当且仅当它满足如下两个条件：

• $1\leq x < y < z\leq n$；
• $y−x\leq z−y$。 定义一个合法三元组 $(x,y,z)$ 的权值为 $a_x+a_y+a_z$。

$q$ 次询问，第 $i$ 次询问会给定一个区间 $[l_i,r_i]$，你需要求出满足 $l_i\leq x<y<z\leq r_i$ 的三元组的最大权值是多少。

$3\leq n\leq5\times10^5,1\leq q\leq5\times10^5,1\leq a_i\leq10^8,1\leq l_i<l_{i+2}\leq r_i\leq n$。

题解

题目要统计三元组 $(i,j,k)$ 满足 $i<j<k$ 且 $a_i+a_j=a_k$。

考虑固定 $k$，我们要求 $a_i + a_j = a_k, \quad i<j<k$。

等价于在 $[1,k-1]$ 内找到一对和为 $a_k$ 的数。

做法：枚举 $j$，检查 $a_k-a_j$ 是否出现过。用哈希/数组标记即可。

总复杂度 $O(n^2)$ 可以接受。若优化，可以用 $\text{map}$ 或二分，做到 $O(n \log n)$。

T4-秩（rank）

题面

定义一个矩阵的秩为对其高斯消元后，非全零行的个数。

定义一张无向图的秩为其邻接矩阵的秩。

给定一棵 $n$ 个点的树，结点从 $1$ 开始标号。你可以任意删除树上的边，请你求出这样 能够得到的 $2^{n−1}$ 种森林的秩之和是多少。

答案对 $998244353$ 取模。 注意，本题矩阵的所有初等行变换都是在实数意义下进行的，而非在模 $2$ 意义下。

$2\leq n\leq5\times10^5,1\leq u<v\leq n$。

题解

这是一个计数问题。题目本质是：给定一棵森林，计算其秩的概率分布。

关键结论：一棵树的秩只和大小有关，设大小为 $n$，其秩分布可以通过递归拆分得到。

设 $f(n)$ 为大小为 $n$ 的树的秩分布，则 $f(n) = \sum_{i=1}^{n-1} f(i) \ast f(n-i-1)$，其中 $\ast$ 表示卷积。

因此整体问题转化为多项式卷积，可以用 NTT 在 $O(n \log n)$ 时间内求出。